/* =============================================================
 * Your Grandmother's guide to Algorithms
 * =============================================================
 *
 * Copyright (c) 2007, Saverio Miroddi
 *
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without 
 * modification, are permitted provided that the following conditions are met:
 * 
 *     * Redistributions of source code must retain the above copyright notice,
 *       this list of conditions and the following disclaimer.
 *     * Redistributions in binary form must reproduce the above copyright 
 *       notice, this list of conditions and the following disclaimer in the 
 *       documentation and/or other materials provided with the distribution.
 *     * Neither the name of the <ORGANIZATION> nor the names of its 
 *       contributors may be used to endorse or promote products derived from 
 *       this software without specific prior written permission.
 * 
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER 
 * OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
 * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
 * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 *  
 * ---------------------------
 * RBTree.java
 * ---------------------------
 *
 */
package redblack;

import static redblack.RBNode.NULL_NODE;

import java.lang.reflect.Array;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

@SuppressWarnings("unchecked")
public class RBTree<T extends Comparable<T>>
{
	private RBNode<T> _root;
	private int _size;
	
	/**
	 * Doesn't accept null values for simplicity, but it's very easy to change.
	 */
	public void insert(T value)
	{
		if (value == null) throw new IllegalArgumentException("null values not accepted");
		
		if (_root == NULL_NODE) {
			// BLACK: this is actually insert case 1
			_root = new RBNode<T>(value, RBNode.BLACK);
		}
		else {
			_root.insert(value, this);
		}
		
		_size++;
	}
	
	public boolean remove(T value)
	{
		if (value == null) throw new IllegalArgumentException("null values not accepted");

		if (_root == NULL_NODE) {
			return false;
		}
		else if (_size == 1) {
			if (_root.value.equals(value)) {
				_root = NULL_NODE;
				_size = 0;
				return true;
			}
			else {
				return false;
			}
		}
		else {
			boolean removed = _root.delete(value, this);
			if (removed) _size--;
			return removed;
		}
	}
	
	public int size()
	{
		return _size;
	}
	
	protected void setRoot(RBNode<T> newRoot)
	{
		_root = newRoot;
	}

	///////////////////////////////////////////////////////////////////////////
	// DEBUG METHODS
	///////////////////////////////////////////////////////////////////////////
	
	public RBNode<T> getRoot()
	{
		return _root;
	}
	
	public T[] toArray(T[] dest)
	{
		Class dataType = dest.getClass().getComponentType();
		dest = (T[])Array.newInstance(dataType, _size);
		
		RBIterator treeItr = iterator();
		for (int i = 0; i < _size; i++) {
			dest[i] = treeItr.next();
			assert(dest[i] != null);
		}

		return dest;
	}
	
	public List<T> toList()
	{
		List<T> list = new ArrayList<T>();
		
		RBIterator treeItr = iterator();
		for (T t = treeItr.next(); t != null; t = treeItr.next()) {
			list.add(t);
		}
		
		return list;
	}
	
	
	private enum Direction { PRE, IN, POST, UP }
	
	/** Thread unsafe */
	public RBIterator iterator()
	{
		return new RBIterator(); 
	}

	/**
	 * Very basic iterator; stop can be recognized when the return value is
	 * null.
	 */
	public class RBIterator
	{
		private RBNode<T> _currNode;
		private Direction _currDir;
		/** Contains the directions the past node[s] must take when going UP. */
		private Deque<Direction> _stack;
		
		protected RBIterator()
		{
			_currNode = _root;
			_currDir = Direction.PRE;
			
			_stack = new ArrayDeque<Direction>();
		}

		/**
		 * Because of the fact the "return value" wipes the stack, we must use
		 * iteration + manual stack.<br>
		 * But remember that to iterate is human, to recurse is divine.
		 * <p>
		 * Interesting fact: internal recursion saves the pointer to the next operation
		 * to call after the return from the call; we use Direction to emulate this
		 * behavior.<br>
		 * This method is so long to mimick the recursion with clarity.
		 * <p>
		 * In Python this should be very clean to implement, via yield().
		 */
		public T next()
		{
			while (_currNode != null) {
				switch(_currDir) {
				case PRE:
					if (_currNode.left != null) {
						_stack.addLast(Direction.IN);
						_currNode = _currNode.left;
						_currDir = Direction.PRE;
						break;
					}
				case IN: // fall-though
					_currDir = Direction.POST;
					return _currNode.value;
				case POST:
					if (_currNode.right != null) {
						_stack.addLast(Direction.UP);
						_currNode = _currNode.right;
						_currDir = Direction.PRE;
						break;
					}
				case UP: // fall-through
					_currNode = _currNode.parent;
					_currDir = _stack.pollLast(); // can get null
					break;
				default:
					throw new AssertionError(_currDir);
				}
			}
			
			// we walked the entire tree
			return null;
		}

//		/** Recursive counterpart. Holy c**p, three lines!! */		
//		public void rekurse(RBNode<T> node)
//		{
//			PRE: if (node.left != null) rekurse(node.left); --> fall-through
//			IN // do some cute action
//			POST: if (node.right != null) rekurse(node.right); --> second fall-through
//		    UP:
//		}
	}
}